# 代码编写者： 李朔
# 开发时间： 2021/9/10 15:24
s=[1,53,22,7,1,4,2,7,12]

def Merge(l_pointer,r_pointer):
    #解决 conquer and 合并 merge
    #合并之后的合并序列
    merge_list=[]
    #一个处理l_pointer,一个处理r_pointer
    process_p_l,process_p_r=0,0
    #当两个指针都还没有走到序列尾部时，我们比较两个序列中对应值的大小，将其加入到合并序列中
    while process_p_l<len(l_pointer) and process_p_r<len(r_pointer):
        if l_pointer[process_p_l]<r_pointer[process_p_r]:
            merge_list.append(l_pointer[process_p_l])
            process_p_l+=1
        else:
            merge_list.append(r_pointer[process_p_r])
            process_p_r+=1
    if process_p_l==len(l_pointer):
        #l_pointer这个序列走完了
        for i in r_pointer[process_p_r:]:
            merge_list.append(i)
    else:
        for i in l_pointer[process_p_l:]:
            merge_list.append(i)
    return merge_list
def Merge_sort(s):
    #divide 分割子字符串
    #分割到每个子序列仅包含一个字符时结束
    if len(s)<=1:
        return s
    #划分的索引位置
    mid_pointer=len(s)//2
    #划分左右子序列
    #左序列为s[:mid-1]
    l_pointer=Merge_sort(s[:mid_pointer])
    #右序列为s[mid:]
    r_pointer=Merge_sort(s[mid_pointer:])
    return Merge(l_pointer,r_pointer)
print(Merge_sort(s))
